/*****************************************************************************
 *   Copyright 2011 ZHUANG Yuan              	                             *
 *   SudokuITS as Final Year Project for BScCS, City University of Hong Kong *
 *                                      									 *
 *   Licensed under the Apache License, Version 2.0 (the "License");         *
 *   you may not use this file except in compliance with the License.        *
 *   You may obtain a copy of the License at                                 *
 *                                                                           *
 *   http://www.apache.org/licenses/LICENSE-2.0                              *
 *                                                                           *
 *   Unless required by applicable law or agreed to in writing, software     *
 *   distributed under the License is distributed on an "AS IS" BASIS,       *
 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.*
 *   See the License for the specific language governing permissions and     *
 *   limitations under the License.                                          *
 *****************************************************************************/

package android.sudoku.its.expert;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import android.sudoku.its.util.GameVariables;

/**
 * A matrix showing candidates for all undetermined cells
 * @author 51158282
 *
 */
public class CandidateMatrix {
	
	// An list of arraylist of length 81 to store candidate values for each cell
	private List<List<Integer>> candidateMatrix;
	// Since a determined cell does not have candidate, assign -1 to the arraylist 
	private List<Integer> determinedCellValue;

	
	public CandidateMatrix(int[][] twoDClues) {			
		determinedCellValue = new ArrayList<Integer>();
		determinedCellValue.add(-1);	
		
		// Initiate candidate matrix
		candidateMatrix = new ArrayList<List<Integer>>();		
		// Initialize candidate matrix to have 1 to 9 as candidates for each undetermined cell and -1 for determined cells
		for (int row = 0; row < GameVariables.HOUSE_SIZE; row++) 
			for (int col = 0; col < GameVariables.HOUSE_SIZE; col++) {
				if (twoDClues[row][col] != 0) // if the cell is a determined cell 
					candidateMatrix.add(determinedCellValue);				
				else {
					// Create an arraylist to store possible candidate for one cell. Initiate this list to contain 1 to 9
					List<Integer> candidateForOneCell = new ArrayList<Integer>();
					for (int j = 1; j < GameVariables.HOUSE_SIZE + 1; j++) 
						candidateForOneCell.add(j);				
					candidateMatrix.add(candidateForOneCell);	
				}
			}		
		
		generateCandidateMatrix(twoDClues);
	}
	
	private List<List<Integer>> addDeterminedCellValue(List<List<Integer>> candidateMatrix, int cellIndex) {
    	
		candidateMatrix.remove(cellIndex);
		candidateMatrix.add(cellIndex, determinedCellValue);
		
		return candidateMatrix;
	}

	/**
	 * Calculate candidates for all cells on the game board to generate a candidate graph
	 * @param clues		a 2D array representing clues on the game board
	 */
	public void generateCandidateMatrix(int[][] clues) {
		// Check row. If a clue exists in a row, remove it from candidates for all cells in this row
		for (int row = 0; row < GameVariables.HOUSE_SIZE; row++) {
			for (int col = 0; col < GameVariables.HOUSE_SIZE; col++) {
				int cellClue = clues[row][col];
				if (cellClue != 0) { // if this cell has a clue in it
					if (! candidateMatrix.get(row * GameVariables.HOUSE_SIZE + col).equals(determinedCellValue)) // if a determined cell still has candidates in it, eliminate those candidates
						candidateMatrix = addDeterminedCellValue(candidateMatrix, row * GameVariables.HOUSE_SIZE + col);
					// Remove from candidates for all cells in this row
					for (int colIndex = 0; colIndex < GameVariables.HOUSE_SIZE; colIndex++) {
						int cellIndex = row * GameVariables.HOUSE_SIZE + colIndex; // cell index in candidate graph
						if (! candidateMatrix.get(cellIndex).equals(determinedCellValue)) {
					        int indexOfValueToBeRemoved = candidateMatrix.get(cellIndex).indexOf(cellClue) ;
					        if (indexOfValueToBeRemoved != -1) {
					        	candidateMatrix.get(cellIndex).remove(indexOfValueToBeRemoved);
					        	if (candidateMatrix.get(cellIndex).size() == 0)
					        		candidateMatrix = addDeterminedCellValue(candidateMatrix, cellIndex);
					        }
						}
					}
				}
			}
		}
		
		// Check column. If a clue exists in a column, remove it from candidates for all cells in this column
		for (int col = 0; col < GameVariables.HOUSE_SIZE; col++) {
			for (int row = 0; row < GameVariables.HOUSE_SIZE; row++) {
				// Get the clue value of a cell
				int cellClue = clues[row][col];
				if (cellClue != 0) {// if this cell has a clue in it
					if (! candidateMatrix.get(row * GameVariables.HOUSE_SIZE + col).equals(determinedCellValue)) // if a determined cell still has candidates in it, eliminate those candidates
						candidateMatrix = addDeterminedCellValue(candidateMatrix, row * GameVariables.HOUSE_SIZE + col);
					// Remove from candidates for all cells in this column
					for (int rowIndex = 0; rowIndex < GameVariables.HOUSE_SIZE; rowIndex++) {
						int cellIndex = rowIndex * GameVariables.HOUSE_SIZE + col; // cell index in candidate graph
						if (! candidateMatrix.get(cellIndex).equals(determinedCellValue)) {
					        int indexOfValueToBeRemoved = candidateMatrix.get(cellIndex).indexOf(cellClue) ;
					        if (indexOfValueToBeRemoved != -1) {
					        	candidateMatrix.get(cellIndex).remove(indexOfValueToBeRemoved);
					        	if (candidateMatrix.get(cellIndex).size() == 0)
					        		candidateMatrix = addDeterminedCellValue(candidateMatrix, cellIndex);
					        }
						}
					}
				}
			}
		}
		
		// Check block.  If a clue exists in a block, remove it from candidates for all cells in this block
		for (int block = 0; block < GameVariables.HOUSE_SIZE; block++) {
			// Get the left top coordinate of a block
			int blockStartRow = (block/3)*3;
			int blockStartCol = (block%3)*3;
			
			for (int row=blockStartRow; row<(blockStartRow + GameVariables.BLOCK_SIDE_LENGTH); row++) 
				for (int col=blockStartCol; col<(blockStartCol + GameVariables.BLOCK_SIDE_LENGTH); col++) {
					int cellClue = clues[row][col];
					if (cellClue !=0) { // if this cell has a clue in it
						if (! candidateMatrix.get(row * GameVariables.HOUSE_SIZE + col).equals(determinedCellValue)) // if a determined cell still has candidates in it, eliminate those candidates
							candidateMatrix = addDeterminedCellValue(candidateMatrix, row * GameVariables.HOUSE_SIZE + col);
						// Remove from candidates for all cells in this block
						for (int rowIndex=blockStartRow; rowIndex<(blockStartRow + GameVariables.BLOCK_SIDE_LENGTH); rowIndex++) {
							for (int colIndex=blockStartCol; colIndex<(blockStartCol + GameVariables.BLOCK_SIDE_LENGTH); colIndex++) {
								int cellIndex = rowIndex * GameVariables.HOUSE_SIZE + colIndex;
								if (! candidateMatrix.get(cellIndex).equals(determinedCellValue)) {
							        int indexOfValueToBeRemoved = candidateMatrix.get(cellIndex).indexOf(cellClue);
							        if (indexOfValueToBeRemoved != -1) {
							        	candidateMatrix.get(cellIndex).remove(indexOfValueToBeRemoved);
							        	if (candidateMatrix.get(cellIndex).size() == 0)
							        		candidateMatrix = addDeterminedCellValue(candidateMatrix, cellIndex);
							        }
								}
							}						
						}
					}
				}
		}
	}
	
	public void updateCandidateMatrixForHiddenPair(int[] candidateToBeRetained, int[] hiddenPairCellIndexes) {
		int cellLength = candidateToBeRetained.length;
		List<Integer> retainedCandidates = new ArrayList<Integer>();
		for (int i = 0; i < cellLength; i ++) 
			retainedCandidates.add(candidateToBeRetained[i]);
			
		for (int i = 0; i < hiddenPairCellIndexes.length; i ++) {
			int cmIndex = hiddenPairCellIndexes[i];
			candidateMatrix.remove(cmIndex);
			candidateMatrix.add(cmIndex, retainedCandidates);
		}
	}
	
	public void updateCandidateMatrixForNakedPair(int[] candidatesToBeRemoved, int[] nakedPairCellIndexes) {
		// Check if the cells belong to a same row, a same column or a same block
		int cellLength = nakedPairCellIndexes.length;
		if (cellLength >= 2) {
			if ((nakedPairCellIndexes[0]/GameVariables.HOUSE_SIZE) == (nakedPairCellIndexes[1]/GameVariables.HOUSE_SIZE)) { // same row
				int rowIndex = nakedPairCellIndexes[0]/GameVariables.HOUSE_SIZE;
				for (int col = 0; col < GameVariables.HOUSE_SIZE; col ++) {
					int cellIndex = rowIndex * GameVariables.HOUSE_SIZE + col;
					if (candidateMatrix.get(cellIndex) != determinedCellValue) // this cell is not a determined cell
						// This cell does not belong to the naked pair cells and has more than one candidate
						if ((!ifIntArrContainsNum(nakedPairCellIndexes, cellIndex)) && (candidateMatrix.get(cellIndex).size() > 1)) 
							for (int i = 0; i < candidatesToBeRemoved.length; i++) 
								if (candidateMatrix.get(cellIndex).contains(candidatesToBeRemoved[i]))
									candidateMatrix.get(cellIndex).remove(new Integer(candidatesToBeRemoved[i]));												
				}
			}
			else if ((nakedPairCellIndexes[0]%GameVariables.HOUSE_SIZE) == (nakedPairCellIndexes[1]%GameVariables.HOUSE_SIZE)) { // same column
				int colIndex = nakedPairCellIndexes[0]%GameVariables.HOUSE_SIZE;
				for (int row = 0; row < GameVariables.HOUSE_SIZE; row ++) {
					int cellIndex = row * GameVariables.HOUSE_SIZE + colIndex;
					if (candidateMatrix.get(cellIndex) != determinedCellValue) // this cell is not a determined cell
						// This cell does not belong to the naked pair cells and has more than one candidate
						if ((!ifIntArrContainsNum(nakedPairCellIndexes, cellIndex)) && (candidateMatrix.get(cellIndex).size() > 1)) 
							for (int i = 0; i < candidatesToBeRemoved.length; i++) 
								if (candidateMatrix.get(cellIndex).contains(candidatesToBeRemoved[i]))
									candidateMatrix.get(cellIndex).remove(new Integer(candidatesToBeRemoved[i]));								
				}
			}
			else { // same block
				int rowIndex = nakedPairCellIndexes[0]/GameVariables.HOUSE_SIZE;
				int colIndex = nakedPairCellIndexes[0]%GameVariables.HOUSE_SIZE;
				int blockStartRowIndex = (rowIndex/GameVariables.BLOCK_SIDE_LENGTH)*GameVariables.BLOCK_SIDE_LENGTH;
				int blockStartColIndex = (colIndex/GameVariables.BLOCK_SIDE_LENGTH)*GameVariables.BLOCK_SIDE_LENGTH;
				for (int row = 0; row < GameVariables.BLOCK_SIDE_LENGTH; row++) {
					for (int col = 0; col < GameVariables.BLOCK_SIDE_LENGTH; col++) {
						int cellIndex = (row + blockStartRowIndex) * GameVariables.HOUSE_SIZE + (col + blockStartColIndex);
						if (candidateMatrix.get(cellIndex) != determinedCellValue) // this cell is not a determined cell
							// This cell does not belong to the naked pair cells and has more than one candidate
							if ((!ifIntArrContainsNum(nakedPairCellIndexes, cellIndex)) && (candidateMatrix.get(cellIndex).size() > 1)) 
								for (int i = 0; i < candidatesToBeRemoved.length; i++) 
									if (candidateMatrix.get(cellIndex).contains(candidatesToBeRemoved[i]))
										candidateMatrix.get(cellIndex).remove(new Integer(candidatesToBeRemoved[i]));													
					}
				}
				
			}
		}
					
	}
	
	private boolean ifIntArrContainsNum(int[] intArr, int num) {
		boolean ifIntArrContainsNum = false;
		
		for (int i = 0; i < intArr.length; i ++)
			if (intArr[i] == num)
				return ifIntArrContainsNum = true;
		
		return ifIntArrContainsNum;
	}
	
	/**
	 * Update the Candidate Matrix once a number is input on the game board
	 * @param num		the number input by the user
	 * @param nRow		the row index of the input position
	 * @param nCol		the column index of the input position
	 */
	public void updateCandidateMatrixByInputNumber(int num, int nRow, int nCol) {
		// update row
		for (int colIndex = 0; colIndex < GameVariables.HOUSE_SIZE; colIndex++) {
			int cellIndex = nRow * GameVariables.HOUSE_SIZE + colIndex; // cell index in candidate graph
			if (! candidateMatrix.get(cellIndex).equals(determinedCellValue)) {
		        int indexOfValueToBeRemoved = candidateMatrix.get(cellIndex).indexOf(num) ;
		        if (indexOfValueToBeRemoved != -1) {
		        	if (candidateMatrix.get(cellIndex).size() != 1)
		        		candidateMatrix.get(cellIndex).remove(indexOfValueToBeRemoved);
		        	else
		        		candidateMatrix.set(cellIndex, determinedCellValue);
		        }		        		       
			}			
		}
		
		// update column
		for (int rowIndex = 0; rowIndex < GameVariables.HOUSE_SIZE; rowIndex++) {
			int cellIndex = rowIndex * GameVariables.HOUSE_SIZE + nCol; // cell index in candidate graph
			if (! candidateMatrix.get(cellIndex).equals(determinedCellValue)) {
		        int indexOfValueToBeRemoved = candidateMatrix.get(cellIndex).indexOf(num) ;
		        if (indexOfValueToBeRemoved != -1) {
		        	if (candidateMatrix.get(cellIndex).size() != 1)
		        		candidateMatrix.get(cellIndex).remove(indexOfValueToBeRemoved);
		        	else
		        		candidateMatrix.set(cellIndex, determinedCellValue);
		        }	
			}
		}
				
		// update block
		int blockStartRow = (nRow/3)*3; 
		int blockStartCol = (nCol/3)*3;
		for (int rowIndex=blockStartRow; rowIndex<(blockStartRow + GameVariables.BLOCK_SIDE_LENGTH); rowIndex++) {
			for (int colIndex=blockStartCol; colIndex<(blockStartCol + GameVariables.BLOCK_SIDE_LENGTH); colIndex++) {
				int cellIndex = rowIndex * GameVariables.HOUSE_SIZE + colIndex;
				if (! candidateMatrix.get(cellIndex).equals(determinedCellValue)) {
			        int indexOfValueToBeRemoved = candidateMatrix.get(cellIndex).indexOf(num);
			        if (indexOfValueToBeRemoved != -1) {
			        	if (candidateMatrix.get(cellIndex).size() != 1)
			        		candidateMatrix.get(cellIndex).remove(indexOfValueToBeRemoved);
			        	else
			        		candidateMatrix.set(cellIndex, determinedCellValue);
			        }	
				}
			}
		}
	}
	
	public List<List<Integer>> getCandidateMatrix() {
		return candidateMatrix;
	}
	
	/**
	 * TODO delete this is a test function upon finishing
	 * @return
	 */
	public int[][] getIntArrCandidateMatrix() {
		int[][] intArrCandidateMatrix = new int[GameVariables.PUZZLE_LENGTH][GameVariables.HOUSE_SIZE];
		
		for (int i=0; i<GameVariables.PUZZLE_LENGTH; i++) {
			for (int j=0; j<GameVariables.HOUSE_SIZE; j++) {
					intArrCandidateMatrix[i][j] = 0;
			}
		}
		
		for (int i = 0; i < GameVariables.PUZZLE_LENGTH; i++) {
		    Iterator<Integer> iterator = candidateMatrix.get(i).iterator();
		    for (int j = 0; j < candidateMatrix.get(i).size(); j++) {
		    	int value = iterator.next().intValue();
		    	if (value != -1)
			    	intArrCandidateMatrix[i][value - 1] = value;
		    }
		}
			
		return intArrCandidateMatrix;
	}
	
	/*
	 * Sort arraylist
	 * http://www.java-examples.com/sort-elements-java-arraylist-example
	 * 
	 * */
}
